The Enterprise is called to Deep Space Station K7 by a priority 1 distress call. The space station and planet are in a quadrant disputed between the Federation and Klingon Empire. The quadrant was the site of the battle of Domatu 5, which occurred 23 years ago. The terms of the Organian peace treaty were that the Sherman's planet would revert to whichever side could manage it most efficiently.
Kirk is furious after the distress call issued by Nilz Barris, Undersecretary in Charge of Agriculture in this quadrant and person in charge of the development of the planet's development, turns out to have been without justification. In fact, Barris just wants someone to guard the quadrotriticale grain (a four-lobed high yield variety) bound for Sherman's Planet. Barris's assistant is Arne Darvin, and Mr. Lurry is the manager of the space station.
A Klingon ship arrives at the space station and requests that its crew be granted shore leave. Kirk tells the Klingon leader Koloth that he can bring members of his crew down 12 at a time, but that he will provide one security guard for each Klingon which beams down.
Meanwhile, the intergalactic trader Cyrano Jones gives Uhura a trilling creature called a tribble. She brings it to the Enterprise, where it promptly begins reproducing. Jones also tries to sell tribbles to Klingons on the Station, but the tribbles respond by emitting high-pitched yelps. Trouble breaks out between Klingons and members of the Enterprise's crew, also on shore leave, when one of the Klingons compares Earthers to Regulan bloodworms. This infuriates Chekov, who then becomes more upset when the Klingon goes on to call Kirk a swaggering, overbearing, tin-plated, dictator with delusions of godhood. However, Scott holds Chekov back, even after the Klingon calls Kirk a Denebrian slime devil. However, when the Klingon calls the Enterprise a sagging old rust-bucket which is designed like a garbage scull, Scott punches him, precipitating a bar room brawl. When Kirk questions his crew, no one admits to starting the fight. However, when Kirk questions Scott alone, he admits that he started the fight, and also reveals that he refrained from fighting while Kirk was being insulted, but was forced to take action when the Klingons insulted the Enterprise.
The tribbles begin proliferating throughout the Enterprise, and Kirk even accidentally sits on one while taking a seat in his command chair. Kirk orders Uhura to clean the tribbles off the ship, and beams down to the space station to confront Cyrano Jones. However, since the only animals it is illegal to transport are dangerous one (and tribbles are not dangerous), Kirk can do nothing.
After Kirk finds that tribbles have spread aboard the Enterprise through air vents, he becomes concerned that they may have infested the grain storage lockers on the space station as well. His hunch proves correct, and opening the overhead storage bin produces a rain of tribbles on Kirk's head. Spock calculates that 1,771,561 tribbles are likely to exist on the station, assuming each tribble has a litter of 10 every 12 hours over a period of 3 days. However, Spock notes that, inexplicably, many of the tribbles are dead.
When the station transporter room is being cleared of tribbles, one of them yelps at Barris's assistant Darvin. Kirk verifies that tribbles coo for humans (and even Vulcans; ``obviously the tribbles are very perceptive creatures,'' according to Spock), but yelp for Klingons. He then asks McCoy to perform a tricorder a scan of Darvin. McCoy verifies that that Darvin is a Klingon, and also reveals that the grain was poisoned. Darvin admits to being a Klingon agent and to be responsible for poisoning the grain. Darvin is arrested, Kirk tells the Klingons to leave Federation territory, and Jones is ordered to pick up every tribble on the space station, a task which Spock estimates will take 17.9 years.
Luckily, another freighter can be diverted to provide replacement grain for Sherman's planet. However, this does not solve the problem of de-tribbling the Enterprise. The tribbles are finally removed from the Enterprise when Scotty transports them aboard the Klingon ship. While the tribbles may not enjoy their new home, the Klingons will definitely not enjoy their new passengers.